home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / qsam300.zip / QSAM300.DOC < prev    next >
Encoding:
Text File  |  1989-04-05  |  20.0 KB  |  533 lines
  1.  
  2.                            A B-Tree Access Method
  3.                          for QuickBASIC Programmers.
  4.  
  5.                         QSAM 3.0 (C)1989 Cornel Huth
  6.  
  7.  
  8.         Feel free to use QSAM in any program of yours.  No registration
  9.         or payment is required.  If you want the source code send $20.00
  10.         to:
  11.  
  12.                             Cornel Huth
  13.                             ATTN: QSAM SOURCE
  14.                             6402 Ingram Rd.
  15.                             San Antonio, TX  78238
  16.  
  17.  
  18.             I will send you the latest version of QSAM source on
  19.             5ΒΌ" DS/DD IBM-readable diskette.  The source includes
  20.             the QSAM low-level stuff (written in MASM-compatible
  21.             assembly) and the QuickBASIC 4.0 I/O and interface.
  22.  
  23.  
  24.         -----------------------------------------------------------------
  25.         QSAM is a keyed-file system based on the b-tree sorting method.
  26.         In addition to finding any particular key and its associated
  27.         data record very quickly, QSAM allows sequential access to
  28.         the data file (not usually found in b-tree access programs).
  29.  
  30.         This program was originally created by Rick Grehan for Turbo-C.
  31.         He has submitted it to the public domain and I thank him for that
  32.         and the nice work he did on the very readable assembly code.
  33.  
  34.         What you should find in the QSAM package is the QSAM300.LIB,
  35.         QSAM300.DOC, and QSTEST.BAS and QSAM300.BI.
  36.  
  37.         Add QSAM300.LIB to your standard library if you like, and then
  38.         LINK /QU it into a QLB library for the environment.
  39.  
  40.                 C>lib yourstd.lib +qsam300.lib;
  41.  
  42.                 C>link /qu yourstd.lib,qb.qlb,nul,bqlb40.lib
  43.  
  44.  
  45.  
  46.  
  47.         -----------------------------------------------------------------
  48.         Interface summary:
  49.  
  50.         All QSAM routines are FUNCTIONs and return an integer code
  51.         which is detailed in Error Codes.  These must be DECLAREd.
  52.  
  53.          1)  Qcreatkf%(filename$,keylen%,kftype$)
  54.          2)  Qcreatdf%(filename$,reclen%)
  55.          3)  Qopenk%(filename$,fileno%)
  56.          4)  Qopend%(filename$,fileno%)
  57.          5)  Qcreatkr%(kfile%,dfile%,Qkey$,Qrec$)
  58.          6)  Qreadkr%(kfile%,dfile%,Qkey%,Qrec$)
  59.          7)  Qreadnkr%(kfile%,dfile%,Qkey$,Qrec$)
  60.          8)  Qinsertk%(kfile%,dfile%,Qkey$)
  61.          9)  Qwritedr%(dfile%,Qrec$)
  62.         10)  Qrewindk%(kfile%)
  63.         11)  Qdelk%(kfile%,Qkey$)
  64.         12)  Qdelkr%(kfile%,dfile%,Qkey$)
  65.         13)  Qclosek%(kfile%)
  66.         14)  Qclosed%(dfile%)
  67.         15)  Qfileattrk%(kfile%,keylen%,keys&,bfileno%,kftype$)
  68.         16)  Qfileattrd%(dfile%,reclen%,recs&,bfileno%,dftype$)
  69.  
  70.         -----------------------------------------------------------------
  71.         Interface detail:
  72.  
  73.          1)  Qcreatkf(filename$,keylen,kftype$)
  74.  
  75.              Create a new, empty key file.  If filename$ exists, its
  76.              header will be overwritten by null data.
  77.  
  78.              filename$ - string.   Pathname of key file to create.
  79.                          Any valid DOS drive/path/filename can be used.
  80.     
  81.              keylen    - integer.  Length of key for this key file.
  82.                          Valid range is 1 to 64 bytes.
  83.  
  84.              kftype$   - string.   For a sorting-only file, kftype$="O".
  85.                          For an indexing file, kftype$ = "K".  "O" is
  86.                          key-Only and has no associated data file (and
  87.                          data records).  It can be used as a sorting
  88.                          method.  For "K" files, you should create a
  89.                          data file.
  90.  
  91.              filename$ = "C:\HIST\AR89.KEY"
  92.              keylen = 16
  93.              kftype$ = "K"
  94.              stat = Qcreatkf(filename$,keylen,kftype$)
  95.  
  96.  
  97.          2)  Qcreatdf(filename$,reclen)
  98.  
  99.              Create a new data file.  If filename$ exists, its header
  100.              will be overwritten by null data.
  101.  
  102.              filename$ - string.   Pathname of data file to create.
  103.                          Any valid DOS drive/path/filename can be used.
  104.     
  105.              reclen    - integer.  Length of record for this data file.
  106.                          Valid range is 3 to 32767 bytes.
  107.  
  108.              filename$ = "C:\HIST\AR89.DAT"
  109.              reclen = 128
  110.              stat = Qcreatdf(filename$,reclen)
  111.  
  112.  
  113.          3)  Qopenk(filename$,fileno)
  114.  
  115.              Open an existing key file and associate it with fileno.
  116.              If the file is a key file, a data file will also need
  117.              to be opened.  You may have multiple index files opened for
  118.              a data file.  The fileno is an arbitrary number.  It does
  119.              not reflect either a BASIC handle nor a DOS handle.  It is,
  120.              however, used to reference the key file in any later operation.
  121.              QSAM uses the BASIC FREEFILE function to obtain an
  122.              available channel but hides this from the application.
  123.              Use Qfileattrk() for information on the key file.
  124.  
  125.              filename$ - string.   Pathname of existing key file.
  126.     
  127.              fileno    - integer.  Number to associate the key file
  128.                          with for future operations.  Valid range is
  129.                          0 to 9.
  130.  
  131.              filename$ = "C:\HIST\AR89."
  132.              ARKEY = 0
  133.              ARDAT = 0
  134.              stat = Qopenk(filename$+"KEY",ARKEY)
  135.              if stat = 0 then
  136.                 kfile = fileno
  137.                 stat = Qopend(filename$+"DAT",ARDAT)
  138.  
  139.  
  140.          4)  Qopend(filename$,fileno)
  141.  
  142.              Open an existing data file and associate it with fileno.
  143.              The fileno is an arbitrary number.  It does not reflect
  144.              either a BASIC handle nor a DOS handle.  It is, however,
  145.              used to reference the data file in any later operation.
  146.              Use Qfileattrd() for information on the data file.
  147.  
  148.              filename$ - string.   Pathname of existing data file.
  149.     
  150.              fileno    - integer.  Number to associate the data file
  151.                          with for future operations.  Valid range is
  152.                          0 to 9.
  153.  
  154.              {see Qopenk() for an example}
  155.  
  156.  
  157.          5)  Qcreatkr(kfile,dfile,Qkey$,Qrec$)
  158.  
  159.              Add the key, Qkey$, to the key file, kfile, and the data
  160.              record, Qrec$, to the data file, dfile.  Qkey$ must
  161.              not already exist.  QSAM is case-sensative so it is
  162.              recommended that keys be made upper-case (or lower) unless
  163.              there is a reason not to do this.
  164.  
  165.              kfile     - integer.  Number that was used as fileno in
  166.                          openk().
  167.  
  168.              dfile     - integer.  Number that was used as fileno in
  169.                          opend().
  170.  
  171.              Qkey$     - string.   Key to add to key file.
  172.  
  173.              Qrec$     - string.   Data record to add to the data file
  174.                          that is indexed by Qkey$.
  175.  
  176.              kfile = 0
  177.              dfile = 0
  178.              Qkey$ = acctid$ + acctxn$
  179.              Qrec$ = xaction$
  180.              stat = Qcreatkr(kfile,dfile,Qkey$,Qrec$)
  181.  
  182.  
  183.          6)  Qreadkr(kfile,dfile,Qkey$,Qrec$)
  184.  
  185.              Search for key, Qkey$, in kfile, and if found, retrieve
  186.              the data record from dfile, and place it in Qrec$.
  187.  
  188.              kfile     - integer.  Number that was used as fileno in
  189.                          openk().
  190.  
  191.              dfile     - integer.  Number that was used as fileno in
  192.                          opend().
  193.  
  194.              Qkey$     - string.   Key for which to search in key file.
  195.  
  196.              Qrec$     - string.   Returned data record associated with
  197.                          Qkey$.
  198.  
  199.              kfile = 0
  200.              dfile = 0
  201.              Qkey$ = acctid$ + acctxn$
  202.              stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
  203.  
  204.  
  205.          7)  Qreadnkr(kfile,dfile,Qkey$,Qrec$)
  206.  
  207.              Retrieve the next ordered key in kfile, placing it in Qkey$,
  208.              and place its data record from dfile into Qrec$.  This
  209.              function allows for sequential processing of the data.
  210.  
  211.              kfile     - integer.  Number that was used as fileno in
  212.                          openk().
  213.  
  214.              dfile     - integer.  Number that was used as fileno in
  215.                          opend().
  216.  
  217.              Qkey$     - string.   Returned key which immediately follows
  218.                          the key found in Qreadkr() file.
  219.  
  220.              Qrec$     - string.   Returned data record associated with
  221.                          the returned key, Qkey$.
  222.  
  223.              kfile = 0
  224.              dfile = 0
  225.              Qkey$ = acctid$ + acctxn$
  226.              stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
  227.              if stat = 0 then
  228.                 stat = Qreadnkr(kfile,dfile,Qkey$,Qrec$)
  229.  
  230.  
  231.          8)  Qinsertk(kfile,dfile,Qkey$)
  232.  
  233.              After having found a key, insert the key Qkey$ into the
  234.              key file, kfile, and have associated with it the data
  235.              record that was indexed by the found key.  This allows
  236.              you to add another key to index a particular data record,
  237.              including that from another kfile (multiple indicies per
  238.              data record).
  239.  
  240.              kfile     - integer.  Number that was used as fileno in
  241.                          openk().
  242.  
  243.              dfile     - integer.  Number that was used as fileno in
  244.                          opend().
  245.  
  246.              Qkey$     - string.   Key for which you want to add to the
  247.                          key file, kfile, and have it also point to
  248.                          the data record in dfile of that last found
  249.                          Qkey$ in kfile.
  250.  
  251.              kfile = 1          '{1 of n opened index files to dfile}
  252.              dfile = 0
  253.              Qkey$ = acctid$ + acctxn$
  254.              stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
  255.              if stat = 0 then
  256.                 Qkey$ = acctid$ + timestamp$
  257.                 stat = Qinsertk(kfile,dfile,Qkey$)
  258.  
  259.  
  260.          9)  Qwritedr(dfile,Qrec$)
  261.  
  262.              Overwrite the current data record in dfile with Qrec$.
  263.              This allows you to update the contents of a record
  264.              in a data file.
  265.  
  266.              dfile     - integer.  Number that was used as fileno in
  267.                          opend().
  268.  
  269.              Qrec$     - string.   Data to use in replacing the previous
  270.                          data in dfile.
  271.  
  272.              kfile = 0
  273.              dfile = 0
  274.              Qkey$ = acctid$ + acctxn$
  275.              stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
  276.              if stat = 0 then
  277.                 Qrec$ = Qrec$ + note$
  278.                 stat = Qwritedr(dfile,Qrec$)
  279.  
  280.  
  281.         10)  Qrewindk(kfile)
  282.  
  283.              Position the key file, kfile, to the first key.
  284.  
  285.              kfile     - integer.  Number that was used as fileno in
  286.                          openk().
  287.  
  288.              kfile = 0
  289.              stat = Qrewindk(kfile)
  290.  
  291.  
  292.         11)  Qdelk(kfile,Qkey$)
  293.  
  294.              Delete the key, Qkey$, from kfile.  The data record
  295.              associated with Qkey$ is not affected.  This is necessary
  296.              since you may have multiple keys pointing to the same
  297.              data record.
  298.  
  299.              kfile     - integer.  Number that was used as fileno in
  300.                          openk().
  301.  
  302.              Qkey$     - string.   Key to remove from kfile.
  303.  
  304.              kfile = 0
  305.              Qkey$ = acctid$ + acctxn$
  306.              stat = Qdelk(kfile,Qkey$)
  307.  
  308.  
  309.         12)  Qdelkr(kfile,dfile,Qkey$)
  310.  
  311.              Delete the key, Qkey$, from file kfile and also delete
  312.              the associated record from dfile.  Any other keys that
  313.              are also tagged to that record will be invalid.
  314.  
  315.              kfile     - integer.  Number that was used as fileno in
  316.                          openk().
  317.  
  318.              dfile     - integer.  Number that was used as fileno in
  319.                          opend().
  320.  
  321.              Qkey$     - string.   Key for which you want to delete from
  322.                          the key file, kfile, and also delete its
  323.                          associated data record in dfile.
  324.  
  325.              kfile = 0
  326.              dfile = 0
  327.              Qkey$ = acctid$ + acctxn$
  328.              stat = Qdelkr(kfile,dfile,Qkey$)
  329.  
  330.  
  331.         13)  Qclosek(kfile)
  332.  
  333.              Close the key file, kfile.  This is essential for proper
  334.              termination in QSAM.  Header information is written only
  335.              when the file is closed.  Do not rely on QuickBASIC to do
  336.              this, since it won't.
  337.  
  338.              kfile     - integer.  Number that was used as fileno in
  339.                          openk().
  340.  
  341.              kfile = 0
  342.              stat = Qclosek(kfile)
  343.  
  344.  
  345.         14)  Qclosed(dfile)
  346.  
  347.              Close the data file, dfile.  This is essential for proper
  348.              termination in QSAM.
  349.  
  350.              dfile     - integer.  Number that was used as fileno in
  351.                          opend().
  352.  
  353.              dfile = 0
  354.              stat = Qclosed(dfile)
  355.  
  356.  
  357.         15)  Qfileattrk(kfile,keylen,keys&,bfileno,kftype$)
  358.  
  359.              Return information about the key file, kfile.
  360.  
  361.              kfile     - integer.  Number that was used as fileno in
  362.                          openk().
  363.  
  364.              keylen    - integer.  Returned length of keys for kfile.
  365.  
  366.              keys&     - long.     Returned number of keys in kfile.
  367.  
  368.              bfileno   - integer.  Returned BASIC's file number for kfile.
  369.  
  370.              kftype$   - string.   Returned file type, "K" or "O".
  371.  
  372.              kfile = 0
  373.              stat = Qfileattrk(kfile,keylen,keys&,bfileno,kftype$)
  374.  
  375.  
  376.         16)  Qfileattrd(dfile,reclen,recs&,bfileno,dftype$)
  377.  
  378.              Return information about the data file, dfile.
  379.  
  380.              dfile     - integer.  Number that was used as fileno in
  381.                          opend().
  382.  
  383.              reclen    - integer.  Returned length of records for dfile.
  384.  
  385.              recs&     - long.     Returned number of records in dfile.
  386.  
  387.              bfileno   - integer.  Returned BASIC's file number for dfile.
  388.  
  389.              dftype$   - string.   Returned file type, always "S".
  390.  
  391.              dfile = 0
  392.              stat = Qfileattrd(dfile,reclen,recs&,bfileno,dftype$)
  393.  
  394.  
  395.         -----------------------------------------------------------------
  396.         Error Codes:
  397.  
  398.            200  Key not found           206  Data pointer invalid
  399.            201  Key already exists      207  Key pointer invalid
  400.            202  End of file             208  File not QSAM
  401.            203  reserved                209  reserved
  402.            204  Empty file              210  QSAM stack overflow (20 levels)
  403.            205  reserved                211  Function not implemented
  404.  
  405.            220  Data record length invalid
  406.            221  Key length invalid
  407.            222  Invalid key file type
  408.  
  409.         -----------------------------------------------------------------
  410.         Technical Specifications:
  411.  
  412.             Key length:  1 - 64 bytes (ASCII sort), constant
  413.          Record length:  3 - 32767 bytes, constant (avail memory)
  414.              Node size:  512 bytes
  415.          Keys per node:  7 - 84 keys, (512-3)\(keylen+5)
  416.          Max keys/file:  16 million keys
  417.          Max data/file:  16 million bytes
  418.          Max key files:  10 opened at one time
  419.         Max data files:  10 opened at one time
  420.  
  421.  
  422.         Key file header format (first sector (512 bytes) of key file):
  423.  
  424.            filetype        char    ;  0 file type, "K" or "O"
  425.            rootnode        int     ;  1 sector in file of root node
  426.            nokeyslo        int     ;  3 number of keys (low word)
  427.            nokeyshi        byte    ;  5 number of keys (high byte)
  428.            keyavsec        int     ;  6 key available list head
  429.            nxkeysec        int     ;  8 next free sector
  430.            keylen          byte    ; 10 length of key
  431.            maxkeys         byte    ; 11 maximum keys per node
  432.            filler          any     ; 12 - 511 transient data
  433.  
  434.  
  435.         Data file header format (first 32 bytes of data file):
  436.  
  437.            filetype        char    ;  0 file type, "S"
  438.            reclen          int     ;  1 length of record
  439.            norecslo        int     ;  3 number of records (low word)
  440.            norecshi        byte    ;  5 number of records (high byte)
  441.            datavlo         int     ;  6 data available list (low word)
  442.            datavhi         byte    ;  8 data available list (high byte)
  443.            nxdalo          int     ;  9 next data record avail (low word)
  444.            nxdahi          byte    ; 11 next data record avail (high byte)
  445.            filler          any     ; 12 - 31 transient data
  446.  
  447.  
  448.         Key format:
  449.  
  450.            Beginning each node (sector) is a count key byte.  This
  451.            is the count of keys on that sector.  Then for each key
  452.            is a 16-bit previous node pointer, the key itself, the
  453.            24-bit data pointer for that key, and a 16-bit next node
  454.            pointer.
  455.  
  456.            02  00 00  KEY001  01 00 00  00 00  KEY002  02 00 00  00 00 ...
  457.            1.    2.     3.       4.       5.     6.       7.       8.   9.
  458.  
  459.            1.  Key count for that node
  460.            2.  Back pointer (in this case there is no previous node)
  461.            3.  The 6-byte ASCII key.
  462.            4.  The 24-bit data record pointer (record 1)
  463.            5.  Forward ptr to next node/back ptr to previous node of KEY002
  464.            6.  The next key
  465.            7.  Its data pointer
  466.            8.  Forward pointer
  467.            9.  unused space to end of sector
  468.  
  469.  
  470.         Data record format:
  471.  
  472.            Straight data after the header.
  473.  
  474.  
  475.  
  476.         QSAM3B.BAS, the I/O and interface portion of QSAM was written
  477.         and compiled with QuickBASIC 4.0.  The QSAM3B.BAS file was
  478.         compiled with the /O option only.  This means that it is
  479.         left to the programmer to ensure that adequate disk space
  480.         is available prior to writting.  If worst comes to worst,
  481.         you can always get the source code and make any adjustments
  482.         that you like.
  483.  
  484.         File I/O is performed by QB code called from QSAM.  Storage
  485.         for the data buffers and headers are allocated in the
  486.         default data area of QB.  QSAM3B.BAS storage allocation is
  487.         as follows:
  488.  
  489.           2 integer arrays (0 to 9) for file handles.
  490.           1 key hdr array (0 to 9) for key file headers, ea 62 bytes.
  491.           1 data hdr array (0 to 9) for data file headers, ea 32 bytes.
  492.           1 key node array (0 to 9) for node buffers, ea 512 bytes.
  493.           1 data buffer array$ (0 to 9) for data record I/O, size
  494.             allocated is equal to that dfile's record length (var-len$).
  495.           1 type variable for interfacing with QSAM low-level.
  496.  
  497.         QSAM3A.ASM, the low-level, blood-and-guts of QSAM, was written
  498.         by Rick Grehan.  The QB implementation was modified by me.
  499.         It is similar to Grehan's ZSAM however it does not use record
  500.         sets.  I found ZSAM's multiple-record sets unreliable.  Many
  501.         bench checks and runs where made but never successful.  However,
  502.         the single-record code I have found to be bug-free except for
  503.         a typo; at PUTKS, he moves BP into ACKYSC.  Should be AX.
  504.  
  505.         -----------------------------------------------------------------
  506.         Tip:  QSAM uses a simple variable, namely a var-len string,
  507.         to get and put data in the data file.  To overcome this,
  508.         you may want to try this trick.  Go ahead and set up your
  509.         TYPEd variable, then allocate enough space in a var-len
  510.         string to copy to and from it.
  511.  
  512.         TYPE dataTYPE
  513.            whatis AS INTEGER
  514.            whatbe AS STRING * 8
  515.            whaton AS LONG
  516.         END TYPE
  517.  
  518.         DIM whatit AS dataTYPE
  519.  
  520.         whatit.whatis = 2
  521.         whatit.whatbe = "right on"
  522.         whatit.whaton = 6&
  523.  
  524.         DIM SHARED thatit$
  525.         thatit$ = SPACE$(LEN(whatit))
  526.  
  527.         MOVMEM VARPTR(whatit.whatis), SADD(thatit$)
  528.         '{or something similar since MOVMEM is not standard QuickBASIC}
  529.         '{now you have the TYPEd variable data in a var-len string that}
  530.         '{can be used as the Qrec$.}
  531.  
  532.         <End of doc>
  533.